package com.huisu;

import com.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/*
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。


* */
public class Test3 {
   private void dfs(int k,int n,int begin, Deque deque, ArrayList<ArrayList<Integer>> lists){
       if (deque.size()==k){
           lists.add(new ArrayList<>(deque));
           return;
       }
       for (int i=begin;i<n;i++){
           deque.addLast(i);
           dfs(k,n,i+1,deque,lists);
           deque.removeLast();
       }
   }
   /* 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
    说明：
    所有数字都是正整数。
    解集不能包含重复的组合。
    示例 1:
    输入: k = 3, n = 7
    输出: [[1,2,4]]

    示例 2:
    输入: k = 3, n = 9
    输出: [[1,2,6], [1,3,5], [2,3,4]]*/
   private void dfs2(int begin,int k,int target,Deque deque, ArrayList<ArrayList<Integer>> lists){
       if (deque.size()==k&&target==0){
           lists.add(new ArrayList<>(deque));
           return;
       }
       for (int i = begin; i < 10; i++) {
           if (target-i<0){
               return;
           }
           deque.addLast(i);
           dfs2(i=1,k,target-1,deque,lists);
           deque.removeLast();
       }
   }//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
    public List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        defs(lists,new ArrayList<>(),used,nums);
        return lists;
    }
    public void defs(List<List<Integer>> lists,List<Integer> list,boolean[] used,int[] nums){

       if (list.size()==nums.length){
           lists.add(new ArrayList<>(list));
           return;
       }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]){
                continue;
            }
            if (i>0&&nums[i-1]==nums[i]&&!used[i-1])
                continue;
            list.add(nums[i]);
            used[i]=true;
            defs(lists,list,used,nums);
            used[i]=false;
            list.remove(list.size()-1);
        }
    }
    public boolean makesquare(int[] nums){
       int sum=0;
       for (int n:nums){
           sum=sum+n;
       }
       if ((sum==0)||(sum%4)!=0){
           return false;
       }
       return bk(sum/4,nums,new int[4],0);
    }
    //输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形

    //target为总和/4 nums给的数组 size 为四条边 index每次遍历开始地址
    public boolean bk(int target,int[] nums,int[] size,int index){
       if (index==4){
           if (size[0]==size[1]&&size[1]==size[2]&&size[2]==size[3]&&size[3]==size[4]){
               return true;
           }else{
               return false;
           }
       }
        for (int i = 0; i < nums.length; i++) {
            if (size[index]+nums[i]>target)
                continue;
            size[i]=size[i]+nums[index];
            if (bk(target,nums,size,index+1))
                return true;
            size[i]=size[i]-nums[index];

        }
        return false;
    }
    //给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
    //
    //回文串 是正着读和反着读都一样的


}
